//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
//
//
//
// 示例 1:
//
// 输入: [7,5,6,4]
//输出: 5
//
//
//
// 限制：
//
// 0 <= 数组长度 <= 50000
//
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 1015 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 归并排序改
function reversePairs(nums: number[]): number {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    let cnt = 0;
    if(nums.length < 2) return 0
    const merge = (left, right) => {
        const tmp = []
        let i = 0, j = 0
        while(i < left.length && j < right.length) {
            if(left[i] <= right[j]) tmp.push(left[i++]) // 左小于右正常
            else {
                //*? 关键就在这里：左大于右就会产生逆序对
                tmp.push(right[j++])
                //? 左右有序，左边当前元素以及之后的元素，都会和 right[j] 产生一个逆序对
                cnt += left.length - i
            }
        }
        return [...tmp, ...left.slice(i), ...right.slice(j)]
    }
    const mergeSort = (arr) => {
        if(arr.length < 2) return arr
        const mid = arr.length >> 1
        const left = arr.splice(0, mid)
        return merge(mergeSort(left), mergeSort(arr))
    }
    mergeSort(nums)
    return cnt
}
//leetcode submit region end(Prohibit modification and deletion)
